package algo.graph;

import ds.adt.Bag;
import ds.adt.Graph;

public class ConnectedComponents {

	private boolean[] marked;
	private int[] id;
	private int count;

	public ConnectedComponents(Graph g) {
		this.marked = new boolean[g.V()];
		this.id = new int[g.V()];
		this.count = 0;

		for (int v = 0; v < g.V(); v++) {
			if (!marked[v]) {
				dfs(g, v);
				count++;
			}
		}
	}

	/**
	 * Does depth first search and marks all the vertices reachable to s in the
	 * graph g.
	 *
	 * @param g
	 * @param s
	 */
	private void dfs(Graph g, int s) {
		marked[s] = true;
		id[s] = count;
		for (Integer w : g.adj(s)) {
			if (!marked[w]) {
				marked[w] = true;
				dfs(g, w);
			}
		}
	}

	public boolean connected(int v, int w) {
		return id[v] == id[w];
	}

	public int id(int v) {
		return id[v];
	}

	public int count() {
		return count;
	}

	public static void main(String[] args) {
		Graph g = new Graph(8);
		g.addEdge(0, 1);
		g.addEdge(1, 2);
		g.addEdge(0, 3);
		g.addEdge(0, 4);
		g.addEdge(5, 6);
		g.addEdge(5, 7);

		System.out.println("Graph : " + g.toString());

		ConnectedComponents cc = new ConnectedComponents(g);
		int N = cc.count();
		System.out.println(N
				+ " connected components are present in the graph.");

		Bag<Integer>[] connected = (Bag<Integer>[]) new Bag[N];
		for (int i = 0; i < N; i++) {
			connected[i] = new Bag<Integer>();
		}

		for (int v = 0; v < g.V(); v++) {
			connected[cc.id(v)].add(v);
		}

		System.out.println("Connected components : ");
		for (int i = 0; i < N; i++) {
			for (int v : connected[i]) {
				System.out.print(v + " ");
			}
			System.out.println();
		}
	}
}
